import collections
from typing import List

from sortedcontainers import SortedList


class FileSharing:

    def __init__(self, m: int):
        self.m = m

        # 空闲用户ID列表
        self.free_user_id = SortedList()
        self.free_user_id.add(1)

        # 文件块被拥有的用户ID列表
        self.chunks = collections.defaultdict(SortedList)

        # 用户拥有文件块列表
        self.users = {}

    def join(self, chunks: List[int]) -> int:
        # 提取最小的空闲用户ID
        user_id = self.free_user_id.pop(0)
        if len(self.free_user_id) == 0:
            self.free_user_id.add(len(self.users) + 2)

        # 记录用户拥有的文件块
        self.users[user_id] = chunks

        # 将用户拥有的文件块更新的文件块列表中
        for chunk in chunks:
            self.chunks[chunk].add(user_id)

        return user_id

    def leave(self, user_id: int) -> None:
        # 将用户拥有的文件块从文件块列表中取出
        for chunk in self.users[user_id]:
            self.chunks[chunk].remove(user_id)
            if len(self.chunks[chunk]) == 0:
                self.chunks.pop(chunk)

        # 清空用户拥有的文件块
        self.users.pop(user_id)

        # 将用户ID添加到空闲用户ID
        self.free_user_id.add(user_id)

    def request(self, user_id: int, chunk: int) -> List[int]:
        if chunk in self.chunks:
            res = list(self.chunks[chunk])
            if user_id not in self.chunks[chunk]:
                self.chunks[chunk].add(user_id)
                self.users[user_id].append(chunk)
            return res
        else:
            return []


if __name__ == "__main__":
    obj = FileSharing(4)
    print(obj.join([1, 2]))  # 1
    print(obj.join([2, 3]))  # 2
    print(obj.join([4]))  # 3
    print(obj.request(1, 3))  # [2]
    print(obj.request(2, 2))  # [1,2]
    obj.leave(1)
    print(obj.request(2, 1))  # []
    obj.leave(2)
    print(obj.join([]))  # 1
    print()

    # 测试用例18/35
    obj = FileSharing(17)
    print(obj.join([]))  # 1
    print(obj.join([6, 8, 7, 15, 16, 9, 10, 4, 13, 12, 5, 14, 1, 11, 2, 17, 3]))  # 2
    print(obj.join([9, 11, 14, 16, 10, 6, 1, 15, 12]))  # 3
    print(obj.join([]))  # 4
    print(obj.join([17, 10, 16]))  # 5
    print(obj.request(1, 6))  # [2,3]
    print(obj.request(1, 1))  # [2,3]
    print(obj.request(1, 13))  # [2]
    print(obj.request(5, 15))  # [2,3]
    print(obj.request(3, 5))  # [2]
    print(obj.request(2, 5))  # [2,3]
    print(obj.request(1, 4))  # [2]
    print(obj.request(1, 7))  # [2]
    print(obj.request(2, 15))  # [2,3,5]
    print(obj.request(3, 5))  # [2,3]
    print(obj.request(2, 1))  # [1,2,3]
